Information has always been a valuable commodity to society. With the advent of computers and digital information exchanges, such as the Internet, the volume of information being generated is exploding. Therefore, the ability to store, access and transmit information quickly and efficiently has become crucial. In particular, with the advent of digital cameras, recorders, scanners and facsimiles (i.e. fax), the ability to store, access and transmit digital images in an efficient manner has found particular importance.
One method of storing, accessing and transmitting data quickly and efficiently involves what is known as data compression and decompression. On a general level, data compression entails the coding of original data into secondary data, from which, the original data can again be derived. Generally, the secondary or coded data, will be quantitatively less than the original data.
Data compression falls into two general categories: lossy and lossless. In a lossy system, data is compressed with the knowledge and foresight that the decompressed data will not be an identical replica of the compressed data, but only a close approximation. Conversely, a lossless system is one that produces an exact replica of the original data from the compressed data. An important technique in the compression of data is known as arithmetic coding. In arithmetic coding, data is typically represented by one or more symbols. An arithmetic encoder takes a stream of input symbols and replaces it with a binary fraction. The binary fraction is a single number, less than 1 and greater than or equal to 0. An arithmetic decoder decodes this single number to create the exact stream of input symbols that went into the encoder. The arithmetic encoder and decoder rely upon set probabilities assigned to each symbol for their proper operation. However, these set probabilities may also be adaptive and the assignment of adaptive probabilities to symbols requires the use of a probability estimator.
In arithmetic coding, an image is represented as a binary fraction between 0 and 1. The range of 0 to 1 defines what is known as an interval. In its simplest form, arithmetic coding assigns a probability between 0 and 1 to a symbol. For example, suppose the input symbol string to be encoded is "ae." Suppose further that the only two symbols to be encoded are "a" and "e" and that they occur in a ratio of three to one (3:1), respectively. Therefore, the probability that "a" will occur is 3/4 or 0.75 and the probability that "e" will occur is 1/4 or 0.25. In this case, "a" is said to be the More Probable Symbol (MPS) and "e" is said to be the Less Probable Symbol (LPS) based on their respective probabilities. Since the first symbol to be encoded is "a", the final code for the input symbol string "ae" must lie inside the "a" range, or between 0 and 0.75. To encode the "e", which follows "a", we further subdivide the now encoded "a" range of 0 to 0.75 proportionately based on the 3:1 "a" to "e" ratio. Therefore, the final code for the input symbol string "ae", after "e" has been encoded, will lie in the range of 0.5625 to 0.75. Taking the middle value of this range, the input symbol string "ae" is now encoded as a fraction of 0.65625. In this fashion, larger input symbol strings can be encoded by the same process of proportionally dividing successive interval ranges based on previously input symbols. The more symbols that are encoded, the smaller the interval range becomes, and the larger the number of significant digits that are required. For a more detailed discussion on arithmetic coding, see Pennebaker, W. B. and J. L. Mitchell, JPEG: Still Image Data Compression Standard (Van Nostrand Reinhold 1993) pp. 135-147.
In 1986, IBM successfully developed an adaptive arithmetic coding architecture to implement an Adaptive Bi-level Image Compression (hereinafter ABIC) standard. The ABIC standard employs an entropy coder and entropy coding concepts. For a more detailed description of the entropy coder and entropy coding concepts, see Pennebaker, W. B., JPEG: Still Image Data Compression Standard, pp. 135-147 (1993). The entropy coder, also known as the "Q-Coder," is more fully described in "Arithmetic Coding Encoder and Decoder System," U.S. Pat. No. 4,905,297, issued to G. G. Langdon, Jr., et al., (hereinafter Langdon Patent) which is hereby fully incorporated by reference. The Q-Coder included an arithmetic coder, decoder and a probability estimator. The Q-coder utilized uncompressed data to determine the LPS probability estimate (Qe) for the data to be compressed and then coded the data based thereon. The decoder functions similarly but in reverse order. The probability estimator updates its probabilities (Qe's) based on successive coding events. In essence, the probability estimator of the Q-Coder improved coder and decoder performance through probability adaptation of the Qe values. Further descriptions of the Q-Coder can also be found in Mitchell, J. L., and W. B. Pennebaker, "Software Implementations of the Q-Coder," IBM Journal of Research and Development, Vol. 32, No. 6, November, 1988, pp. 753-774, and in Arps, R. B. et al., "A Multi-Purpose VLSI Chip for Adaptive Data Compression of Bi-Level Images," IBM Journal of Research and Development, Vol. 32, No. 6, November, 1988, pp. 775-795.
However, in 1988, the Joint Bi-Level Image Experts Group (JBIG) of ISO/IEC JTC1/SC29/WG9 and CCITT SGVIII was formed to establish a standard for the progressive encoding of bi-level images. In 1993, the JBIG Experts Group published International Standard ISO/IEC 11544:1993(E) entitled Information Technology--Coded Representation of Picture and Audio Information--Progressive Bi-Level Image Compression (hereinafter JBIG Standard). The JBIG Standard's implementation of arithmetic coding is also known as the QM-Coder, which describes the coder's technical ancestry to IBM's Q-Coder.
Both the ABIC Q-Coder and the JBIG QM-Coder employ templates to take advantage of observed patterns in an image. A template is a geometric pattern describing the location of pixels relative to a current pixel to be coded. From a template, an integer known as a context is generated and used to identify the index of the state of the adaptive arithmetic coder to be used for coding the current pixel. Templates are well-known in the art and for more information, see International Standard ISO/IEC 11544:1993(E) and Arps, R. B. et al., "A Multi-Purpose VLSI Chip for Adaptive Data Compression of Bi-Level Images," IBM Journal of Research and Development, pp. 775-795 (1988).
The JBIG Standard's QM-Coder outputs Protected Stripe Coded Data (PSCD) that is defined as the bytes of a Stripe Data Entity (SDE) that remain after removing a terminating two bytes. A decoder creates Stripe Coded Data (SCD) from the PSCD by replacing all occurrences of an escape (ESC) byte followed by a "Stuffed" byte with a single ESC byte. The encoder creates the PSCD from the SCD by replacing all occurrences of an ESC byte with an ESC byte followed by a stuff byte. Stuff bytes are 0x00 bytes and are used for unambiguously distinguishing between predefined escape (ESC) bytes, which are 0xff bytes, indicating the start of a marker segment and bytes identical to the escape byte which naturally occur in a compressed data stream. For more information on the PSCD, SCD and ESC bytes, see the International Standard ISO/IEC 11544:1993(E).
The JBIG Standard's QM-Coder defines a method for the compression encoding of a bi-level image (e.g. black and white) that is generally optimized for software implementation. IBM's Adaptive Bi-level Image Compression (ABIC) Q-Coder implements an arithmetic coding algorithm using hardware conventions. Accordingly, since hardware conventions and software conventions need not be the same, and can even be opposite in nature, IBM's ABIC Q-Coder appeared to be incompatible with the JBIG Standard.
U.S. Pat. No. 4,891,643, "Arithmetic Coding Data Compression/Decompression by Selectively Employed, Diverse Arithmetic Coding Encoders and Decoders," issued to Mitchell et al. (hereinafter Mitchell et al.) describes that one may convert between hardware and software conventions for arithmetic coding by inverting data streams according the methods described therein. (See also, J. L. Mitchell and W. B. Pennebaker, "Optimal Hardware and Software Arithmetic Coding Procedures for the Q-Coder," IBM J. Res. Develop., 32, 727-736 (1988)). Therefore, the concept of inverting data streams to arrive at hardware and software compatibility standards in arithmetic coding is well-known in the art. However, with the advent of the JBIG Standard and its particular software conventions, a simple inversion of the data stream according to the teachings of the prior art did not provide the proper coding/decoding compatibility.
Moreover, since logic can be implemented in both software and hardware conventions and since certain logic can be implemented easier in software than in hardware, and vice-versa, the prior art did not provide hardware developers of the JBIG Standard an optimized hardware standard to follow since the JBIG Standard was defined by software conventions. Furthermore, the prior art did not provide a standard for hardware developers for implementing a JBIG Standard and an ABIC standard on a shared and optimized hardware architecture.